package tree.HuffmanTree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTreeDemo {
	public static void main(String[] args) {
		int array[] = {13, 7, 8, 3, 29, 6, 1};
		createHuffmanTree(array);
	}

	//创建 哈夫曼树的方法
	public static Node createHuffmanTree(int[] array) {
		// 1. 为了操作方便，遍历array
		// 2. 把 array 的每个元素变为一个Node
		// 3， 将Node 放入 ArrayList
		List<Node> nodes = new ArrayList<>();
		for (int value : array) {
			nodes.add(new Node(value));
		}


		//循环处理所有数据
		while (nodes.size() > 1) {
			//排序
			//因为 Node 实现了 Comparable，所以这里才可以用
			Collections.sort(nodes);
			System.out.println(nodes);

			//取出根节点权值最小的两个二叉树
			// 1. 取出权值最小的节点
			Node leftNode = nodes.get(0);
			Node rightNode = nodes.get(1);

			// 2. 构建一棵新的二叉树
			//把左子树、右子树的权值加起来得到新的权值
			Node parent = new Node(leftNode.value + rightNode.value);
			parent.left = leftNode;
			parent.right = rightNode;

			// 3. 从array 中删除 已经处理过的节点
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			// 4. 把新的节点加入
			nodes.add(parent);
		}

		//返回 哈夫曼树的 root 节点
		return nodes.get(0);

	}

}

//创建节点
//为了让 Node 对象持续排列 Collecting 集合序列
//让 Node 实现 Comparable
class Node implements Comparable<Node> {
	int value;
	Node left;
	Node right;

	public Node(int value) {
		this.value = value;
	}

	@Override
	public String toString() {
		return "Node{" +
				"value=" + value +
				'}';
	}

	@Override
	public int compareTo(Node o) {
		//表示从小到大排序
		return this.value - o.value;
	}
}
